package busquedasciegas;

import java.util.ArrayList;
import java.util.TreeMap;


public class EstadoPuzzle{	
	
	public EstadoPuzzle padre;
	public Key key;
	protected ArrayList<EstadoPuzzle> descendientes;
	protected boolean visitado;
	
	protected int[] temp;
	private EstadoPuzzle hijo1, hijo2, hijo3, hijo4;
	protected int iHueco;
	protected int jHueco;
	protected int lado;
	
	/**
	 * Crea una instancia de la clase EstadoPuzzle
	 * @param tablero Una representación del tablero
	 * como un ArrayList
	 */
	public EstadoPuzzle(ArrayList<Integer> tablero){
		
		this.key = new Key(new int[tablero.size()]);
		
		for(int i = 0; i < tablero.size(); i++)
			this.key.tablero[i] = tablero.get(i);
				
		this.padre = null;
		this.descendientes = new ArrayList<EstadoPuzzle>();
		this.visitado = false;
		
		hallarHueco();
	}
	
	/**
	 * 
	 * @param tablero Una representación del tablero como vector
	 * de números enteros (int[])
	 * @param padre Una instancia de la clase EstadoPuzzle la cual
	 * representa al padre del nuevo EstadoPuzzle a crear.
	 */
	public EstadoPuzzle(int[] tablero, EstadoPuzzle padre){
		
		this.key = new Key(tablero);
		this.padre = padre;
		this.descendientes = new ArrayList<EstadoPuzzle>();
		this.visitado = false;
		
		hallarHueco();
	}
	
	
	/**
	 * 
	 * @return Dice si el objeto de tipo EstadPuzzle
	 * ya ha sido visitado.
	 */
	public boolean isVisitado() {
		return visitado;
	}
	
	/**
	 * Establece si el objeto ha sido visitado o no.
	 * @param visitado
	 */
	public void setVisitado(boolean visitado) {
		this.visitado = visitado;
	}

	/**
	 * Esta función genera un estado inicial (tablero)
	 * en un orden aleatorio.
	 * @param cuadrados el número de cuadrados del puzzle (9 o 16)
	 * @param aleatorio determina si el nodo debe ser generado 
	 * aleatoriamente.
	 * @return Un estado inicial.
	 */
	public EstadoPuzzle generarNodoInicial(int cuadrados, boolean aleatorio){
		Aleatorio generador = new Aleatorio();
		ArrayList<Integer> tablero = new ArrayList<Integer>();
		ArrayList<Integer> temporal;
		for (int i = 0; i < cuadrados; i++){
			tablero.add(i);
		}
		if (aleatorio){
			temporal = generador.aleatoria(tablero);
			tablero = temporal;
		}
		EstadoPuzzle e = new EstadoPuzzle(tablero);
		return e;
	}
	

	/**
	 * Determina a posición del hueco en el tablero de puzzle
	 */
	public void hallarHueco(){

		int tam = this.key.tablero.length;
		this.lado = (int)Math.sqrt(tam);
		for (int i = 0; i < tam; i++){
			if (this.key.tablero[i] == 0){
				iHueco = (int)Math.floor(i/lado);
				if (i < lado){
					jHueco = i;
				}
				else{
					jHueco = i % lado;
				}
			}
			
		}
	}
	
	
	/**
	 * Esta función aplica los operadores a un estado
	 * con el fin de obtener nuevos estados (descendientes).
	 * @return Una lista con los hijos del estado actual (this).
	 */
	public ArrayList<EstadoPuzzle> generarDescendientes(){
	
		temp = this.key.tablero.clone();
		this.descendientes.clear();
		
		
		if ((iHueco == 0) && (jHueco == 0)){
			temp[0] = this.key.tablero[1];
			temp[1] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			descendientes.add(hijo1);

			temp = this.key.tablero.clone();
			temp[0] = this.key.tablero[lado];
			temp[lado] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo2);
	
		}
		else if ((iHueco == 0) && (jHueco == lado-1)){
			temp[lado-1] = this.key.tablero[1];
			temp[1] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = this.key.tablero.clone();
			temp[lado-1] = this.key.tablero[lado+lado-1];
			temp[lado+lado-1] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
		}
		else if ((iHueco == lado-1) && (jHueco == 0)){
			temp[lado*(lado-1)] = this.key.tablero[lado*(lado-2)];
			temp[lado*(lado-2)] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			
			temp = this.key.tablero.clone();
			temp[lado*(lado-1)] = this.key.tablero[(lado*(lado-1))+1];
			temp[(lado*(lado-1))+1] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
			
		}
		else if ((iHueco == lado-1) && (jHueco == lado-1)){
			temp[(lado*(lado-1))+(lado-1)] = this.key.tablero[(lado*(lado-2))+(lado-1)];
			temp[(lado*(lado-2))+(lado-1)] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = this.key.tablero.clone();
			temp[(lado*(lado-1))+(lado-1)] = this.key.tablero[(lado*(lado-1))+(lado-2)];
			temp[(lado*(lado-1))+(lado-2)] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
		}
		else if (((1 <= iHueco) && (iHueco <= lado-2)) &&
				((1 <= jHueco) && (jHueco <= lado-2))){
			temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco+1))+jHueco];
			temp[(lado*(iHueco+1))+jHueco] = 0;
			hijo1 = new EstadoPuzzle(temp, this);
			
			temp = this.key.tablero.clone();
			temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco-1))+jHueco];
			temp[(lado*(iHueco-1))+jHueco] = 0;
			hijo2 = new EstadoPuzzle(temp, this);
			
			temp = this.key.tablero.clone();
			temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco-1)];
			temp[(lado*iHueco)+(jHueco-1)] = 0;
			hijo3 = new EstadoPuzzle(temp, this);
			
			temp = this.key.tablero.clone();
			temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco+1)];
			temp[(lado*iHueco)+(jHueco+1)] = 0;
			hijo4 = new EstadoPuzzle(temp, this);
			
			descendientes.add(hijo1);
			descendientes.add(hijo2);
			descendientes.add(hijo3);
			descendientes.add(hijo4);
		}
		else{
			if (iHueco == 0){
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco-1)];
				temp[(lado*iHueco)+(jHueco-1)] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco+1)];
				temp[(lado*iHueco)+(jHueco+1)] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco+1))+jHueco];
				temp[(lado*(iHueco+1))+jHueco] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (iHueco == lado-1){
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco-1)];
				temp[(lado*iHueco)+(jHueco-1)] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco+1)];
				temp[(lado*iHueco)+(jHueco+1)] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco-1))+jHueco];
				temp[(lado*(iHueco-1))+jHueco] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (jHueco == 0){
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco-1))+jHueco];
				temp[(lado*(iHueco-1))+jHueco] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco+1))+jHueco];
				temp[(lado*(iHueco+1))+jHueco] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco+1)];
				temp[(lado*iHueco)+(jHueco+1)] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			else if (jHueco == lado-1){
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco-1))+jHueco];
				temp[(lado*(iHueco-1))+jHueco] = 0;
				hijo1 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*(iHueco+1))+jHueco];
				temp[(lado*(iHueco+1))+jHueco] = 0;
				hijo2 = new EstadoPuzzle(temp, this);
				
				temp = this.key.tablero.clone();
				temp[(lado*iHueco)+jHueco] = this.key.tablero[(lado*iHueco)+(jHueco-1)];
				temp[(lado*iHueco)+(jHueco-1)] = 0;
				hijo3 = new EstadoPuzzle(temp, this);
				
				descendientes.add(hijo1);
				descendientes.add(hijo2);
				descendientes.add(hijo3);
			}
			
		}
		return descendientes;
		
	}
	
	public String toString(){
		String tableroString = "";
		for (int i = 0; i < lado; i++){
			for (int j = 0; j < lado; j++){
				tableroString = tableroString + this.key.tablero[(i*lado)+j] + " ";
			}
			tableroString = tableroString + "\n";
		}
		return tableroString;
	}
	
	
	public static void main(String[] args) {
		ArrayList<Integer> tablero = new ArrayList<Integer>();
		tablero.add(0);
		tablero.add(1);
		tablero.add(2);
		tablero.add(3);
		tablero.add(4);
		tablero.add(5);
		tablero.add(6);
		tablero.add(7);
		tablero.add(8);
//		tablero.add(9);
//		tablero.add(10);
//		tablero.add(11);
//		tablero.add(12);
//		tablero.add(13);
//		tablero.add(14);
//		tablero.add(15);
		
		EstadoPuzzle e = new EstadoPuzzle(tablero);
//		for(int i = 0; i < 4; i++)
//			for(int j = 0; j < 4; j++)
//				System.out.println(e.tablero[i][j]);
		EstadoPuzzle nuevoEstado;
		nuevoEstado = e.generarNodoInicial(9, true);
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				System.out.println(nuevoEstado.key.tablero[(i*3)+j]);
		ArrayList<EstadoPuzzle> desc = nuevoEstado.generarDescendientes();
		System.out.println("--- Hijos ---");
		for (EstadoPuzzle hijo : desc) {
			System.out.println("Hijo: ");
			System.out.print(hijo);
		}
		
		TreeMap<Key, EstadoPuzzle> arbol = new TreeMap<Key, EstadoPuzzle>();
		for (EstadoPuzzle estado : desc) {
			arbol.put(estado.key, estado);
		}
		System.out.println("Nodos:");
		for (EstadoPuzzle estado : arbol.values()) {
			System.out.println(estado);
			
		}
		
	}
	
	/**
	 * Clase que representa la llave (key) en la 
	 * estructura de árbol utilizada, la cual es
	 * comparable.
	 * @author german
	 *
	 */
	public class Key implements Comparable<Key>{
		public int[] tablero;
		public Key(int[] tablero){
			this.tablero = tablero;
		}
		
		@Override
		public int compareTo(Key obj1) {
			int comp = 0;
			int tam = this.tablero.length;
			for (int i = 0; i < tam; i++){
				if (this.tablero[i] < (obj1.tablero[i])){
					return -1;
				}
				else if (this.tablero[i] > (obj1.tablero[i])){
					return 1;
				}
				else{
					comp = 0;
				}	
			}
			return comp;
		}
		
	}
}
